package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)100. 相同的树
 * (done)101. 对称二叉树
 * (done)226. 翻转二叉树
 * (done)104. 二叉树的最大深度
 * (done)111. 二叉树的最小深度
 * (done)102. 二叉树的层次遍历
 * (done)107. 二叉树的层次遍历 II
 * (done)404. 左叶子之和
 * (done)257. 二叉树的所有路径
 * @author: jie.deng
 * @time: 2019年1月17日 上午10:11:13
 */
public class MySolution0117 {
	
	/**
	 * 100. 相同的树
	 * 给定两个二叉树，编写一个函数来检验它们是否相同。

   * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
   * 
   * 示例 1:
   * 
   * 输入:       1         1
   *           / \       / \
   *          2   3     2   3
   * 
   *         [1,2,3],   [1,2,3]
   * 
   * 输出: true
   * 示例 2:
   * 
   * 输入:      1          1
   *           /           \
   *          2             2
   * 
   *         [1,2],     [1,null,2]
   * 
   * 输出: false
   * 示例 3:
   * 
   * 输入:       1         1
   *           / \       / \
   *          2   1     1   2
   * 
   *         [1,2,1],   [1,1,2]
   * 
   * 输出: false
	 * @param p
	 * @param q
	 * @return
	 */
	public boolean isSameTree(TreeNode p, TreeNode q) {
//		if (p == null && q == null) {
//			return true;
//		} else if (p == null || q == null) {
//			return false;
//		} else {
//			return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
//		}
		if (p != null && q != null) {
			return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
		}
		return p == q;
	}
    
    /**
     * 101. 对称二叉树
     * 给定一个二叉树，检查它是否是镜像对称的。
     * 
     * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
     * 
     *     1
     *    / \
     *   2   2
     *  / \ / \
     * 3  4 4  3
     * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
     * 
     *     1
     *    / \
     *   2   2
     *    \   \
     *    3    3
     * 说明:
     * 
     * 如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
     * @param root
     * @return
     */
	public boolean isSymmetric(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isSymmetric(root.left, root.right);
	}

	private boolean isSymmetric(TreeNode left, TreeNode right) {
		if (left != null && right != null) {
			return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
		}
		return left == right;
	}
	
	/**
	 * 226. 翻转二叉树
	 * 
     * 翻转一棵二叉树。
     * 
     * 示例：
     * 
     * 输入：
     * 
     *      4
     *    /   \
     *   2     7
     *  / \   / \
     * 1   3 6   9
     * 输出：
     * 
     *      4
     *    /   \
     *   7     2
     *  / \   / \
     * 9   6 3   1
	 * @param root
	 * @return
	 */
    public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		// 当前节点
		TreeNode t = new TreeNode(root.val);
		// 翻转左子树
		TreeNode left = invertTree(root.left);
		if (left != null) {
			t.right = left;
		}
		// 翻转右子树
		TreeNode right = invertTree(root.right);
		if (right != null) {
			t.left = right;
		}
		return t;
    }

	/**
     * 104. 二叉树的最大深度
     * 给定一个二叉树，找出其最大深度。
     * 
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * 
     * 说明: 叶子节点是指没有子节点的节点。
     * 
     * 示例：
     * 给定二叉树 [3,9,20,null,null,15,7]，
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回它的最大深度 3 。
     *      * @param root
     *      * @return
     *      */
	public int maxDepth(TreeNode root) {
		int depth = 0;
		if (root == null) {
			return depth;
		}
		depth += 1; // 加上当前节点深度1
		if (root.left != null && root.right != null) {
			depth += Math.max(maxDepth(root.left), maxDepth(root.right));
		} else {
			if (root.left != null) {
				depth += maxDepth(root.left);
			} else if (root.right != null) {
				depth += maxDepth(root.right);
			}
		}
		return depth;
	}
          
	
	/**
	 * 111. 二叉树的最小深度
	 * 
     * 给定一个二叉树，找出其最小深度。
     * 
     * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * 
     * 说明: 叶子节点是指没有子节点的节点。
     * 
     * 示例:
     * 
     * 给定二叉树 [3,9,20,null,null,15,7],
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回它的最小深度  2.
	 * @param root
	 * @return
	 */
	public int minDepth(TreeNode root) {
		int depth = 0;
		if (null == root) {
			return depth;
		}
		depth += 1; // 加上当前节点深度1
		if (root.left != null && root.right != null) {
			depth += Math.min(minDepth(root.left), minDepth(root.right));
		} else {
			if (root.left != null) {
				depth += minDepth(root.left);
			} else if (root.right != null) {
				depth += minDepth(root.right);
			}
		}
		return depth;
	}

	/**
     * 102. 二叉树的层次遍历
     * 
     * 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
     * 
     * 例如:
     * 给定二叉树: [3,9,20,null,null,15,7],
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回其层次遍历结果：
     * 
     * [
     *   [3],
     *   [9,20],
     *   [15,7]
     * ]
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> rootList = new ArrayList<List<Integer>>();
		levelOrder(root, 0, rootList);
		return rootList;
    }
    
	private void levelOrder(TreeNode t, int level, List<List<Integer>> rootList) {
		if (t == null) {
			return;
		}
		List<Integer> levelList = null;
		if (rootList.size() > level) {
			levelList = rootList.get(level);
		} else {
			levelList = new ArrayList<Integer>();
			rootList.add(levelList);
		}
		levelList.add(t.val);
		levelOrder(t.left, level + 1, rootList);
		levelOrder(t.right, level + 1, rootList);
	}

	/**
     * 107. 二叉树的层次遍历 II
     * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     * 
     * 例如：
     * 给定二叉树 [3,9,20,null,null,15,7],
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回其自底向上的层次遍历为：
     * 
     * [
     *   [15,7],
     *   [9,20],
     *   [3]
     * ]
     * @param root
     * @return
     */
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> rootList = new ArrayList<List<Integer>>();
		levelOrderBottom(root, 0, rootList);
		Collections.reverse(rootList);
		return rootList;
	}

	private void levelOrderBottom(TreeNode t, int level, List<List<Integer>> rootList) {
		if (t == null) {
			return;
		}
		List<Integer> levelList = null;
		if (rootList.size() > level) {
			levelList = rootList.get(level);
		} else {
			levelList = new ArrayList<Integer>();
			rootList.add(levelList);
		}
		levelList.add(t.val);
		levelOrderBottom(t.left, level + 1, rootList);
		levelOrderBottom(t.right, level + 1, rootList);
	}

    /**
     * 404. 左叶子之和
     * 
     * 计算给定二叉树的所有左叶子之和。
     * 
     * 示例：
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 
     * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(TreeNode root) {
    	int sum = 0;
		if (root != null) {
			TreeNode left = root.left; // 左孩子
			if (left != null && left.left == null && left.right == null) {
				// 左叶子
				sum += left.val;
			} else {
				sum += sumOfLeftLeaves(root.left);
			}
			sum += sumOfLeftLeaves(root.right);
		}
		return sum;
    }
    
    /**
     * 257. 二叉树的所有路径
     * 
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     * 
     * 说明: 叶子节点是指没有子节点的节点。
     * 
     * 示例:
     * 
     * 输入:
     * 
     *    1
     *  /   \
     * 2     3
     *  \
     *   5
     * 
     * 输出: ["1->2->5", "1->3"]
     * 
     * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
		List<String> list = new ArrayList<String>();
		if (root == null) {
			return list;
		}
		if (root.left == null && root.right == null) {
			list.add("" + root.val);
			return list;
		}
		binaryTreePaths(root.left, list, "" + root.val);
		binaryTreePaths(root.right, list, "" + root.val);
		return list;
    }

	private void binaryTreePaths(TreeNode t, List<String> list, String str) {
		if (t != null && t.left == null && t.right == null) {
			// t为叶子节点
			list.add(str + "->" + t.val);
		} else if (t != null) {
			binaryTreePaths(t.left, list, str + "->" + t.val);
			binaryTreePaths(t.right, list, str + "->" + t.val);
		}
	}
    
    
}
